Submodular maximization subject to a p-matchoid constraint has various applications in machine learning, particularly in tasks such as feature selection, video and text summarization, movie recommendation, graph-based learning, and constraintbased optimization. We study this problem in the dynamic setting, where a sequence of insertions and deletions of elements to a p-matchoid M(V,I) occurs over time and the goal is to efficiently maintain an approximate solution. We propose a dynamic algorithm for non-monotone submodular maximization under a p-matchoid constraint. For a p-matchoid M(V,I) of rank k, defined by a collection of m matroids, our algorithm guarantees a (2p +2 p p(p +1) +1 +ϵ)-approximate solution at any time t in the update sequence, with an expected amortized query complexity of O(ϵ 3 pk4 log2(k)) per update.

This work studies a novel subset selection problem called max-min diversification with monotone submodular utility (MDMS), which has a wide range of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal of MDMS is to maximize f(S) = g(S)+λ div(S) subject to a cardinality constraint |S| k, where g(S)is a monotone submodular function and div(S) = minu,v S:u =v dist(u,v)is the max-min diversity objective. We propose the GIST algorithm, which gives a 1/2-approximation guarantee for MDMS by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate within a factor of 0.5584. Finally, we show in our empirical study that GISToutperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet.

Given a collection of monotone submodular functions, the goal of Two-Stage Submodular Maximization (2SSM) [Balkanski et al., 2016] is to restrict the ground set so an objective selected u.a.r.

We consider the problem of nonnegative submodular maximization in the online setting. At time step t, an algorithm selects a set St C 2V where C is a feasible family of sets. An adversary then reveals a submodular function ft. The goal is to design an efficient algorithm for minimizing the expected approximate regret. In this work, we give a general approach for improving regret bounds in online submodular maximization by exploiting "first-order" regret bounds for online linear optimization. For monotone submodular maximization subject to a matroid, we give an efficient algorithm which achieves a (1 c/e ε)-regret of O( p kTln(n/k)) where n is the size of the ground set, k is the rank of the matroid, ε > 0 is a constant, and cis the average curvature. Even without assuming any curvature (i.e., taking c = 1), this regret bound improves on previous results of Streeter et al. (2009) and Golovin et al. (2014). For nonmonotone, unconstrained submodular functions, we give an algorithm with 1/2-regret O( nT), improving on the results of Roughgarden and Wang (2018). Our approach is based on Blackwell approachability; in particular, we give a novel first-order regret bound for the Blackwell instances that arise in this setting.

Another example is when expected advertising revenue if we set τ = max{f(X): X U}, SCP asks to find the set of minimum size in U that achieves measure how effectively a subset X summarizes the entire dataset U [Tschiatschek et al., 2014].

Neural Information Processing Systems http://nips.cc/

Neural Information Processing Systems http://nips.cc/

Non-monotone constrained submodular maximization plays a crucial role in various machine learning applications.